/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/search-in-rotated-sorted-array
   @Language: C++
   @Datetime: 19-06-04 17:26
   */

class Solution {
public:
	int search(vector<int>& nums, int target) {
		int n=nums.size(), pos=0;
		if(n==0) return -1;
		for(pos=0; ++pos<n;){
			nums.push_back(nums[pos-1]);
			if(nums[pos-1]>nums[pos]) break;
		}
		if(pos==n) pos=0;
		auto i=lower_bound(nums.begin()+pos,nums.end(),target);
		if(i==nums.end() || *i!=target) return -1;
		return (i-nums.begin())%n;
	}
};
